﻿#pragma once
#include<string>
#include<iostream>
#include<vector>


using namespace std;


// 请完成哈希表的如下操作
// 哈希函数采用除留余数法﻿
template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

// 哈希表中支持字符串的操作
template<>
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;
			hash += e;
		}

		return hash;
	}
};




//哈希桶/拉链法
namespace hash_bucket
{
	template<class T>
	struct HashNode
	{
		T _data;
		HashNode<T>* _next;
		HashNode(const T& data)
			:_data(data)
			, _next(nullptr)
		{}
	};

	//前置哈希表声明
	template<class K, class T, class KeyOfT, class Hash>
	class HashTable;

	//哈希表迭代器
	template<class K,class T,class Ptr,class Ref,class KeyOfT,class Hash = HashFunc<K>>
	struct HashTableIterator
	{
		typedef HashNode<T> Node;
		typedef HashTable<K, T, KeyOfT,Hash> HashBucket;
		typedef HashTableIterator Self;

		HashTableIterator(Node* node,const HashTable<K, T, KeyOfT,Hash>* pht)
			:_node(node)
			, _pht(pht)
		{

		}


		Self& operator++()
		{
			Hash hashfun;
			KeyOfT kot;
			Node* cur = _node;

			if (_node->_next)
			{
				_node = _node->_next;
			}
			else
			{
				int hashi = hashfun(kot(cur->_data)) % _pht->_tables.size();
				++hashi;

				while (hashi < _pht->_tables.size() && _pht->_tables[hashi] == nullptr)
				{
					++hashi;
				}

				if (hashi >= _pht->_tables.size())
				{
					_node = nullptr;
					return *this;
				}

				_node = _pht->_tables[hashi];

			}

			return  *this;
		}


		Ref operator*()
		{
			return _node->_data;
		}
		Ptr operator->()
		{
			return &_node->_data;
		}

		//因为end()返回为一个临时对象，必须加const
		bool operator!=(const Self& ito)
		{
			return _node != ito._node;
		}


		Node* _node;
		const HashBucket* _pht;
	};


	// Hash将key转化为整形，因为哈希函数使用除留余数法
	template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
	class HashTable
	{
	public:
		typedef HashNode<T> Node;
		typedef HashTableIterator<K, T,T*, T&, KeyOfT> Iterator;
		typedef HashTableIterator<K, T,const T*,const T&, KeyOfT> ConstIterator;
		template<class K, class T, class KeyOfT,  class Ptr, class Ref, class Hash>
		friend struct HashTableIterator;
	public:
		HashTable()
		{
			_tables.resize(10, nullptr);
		}

		// 哈希桶的销毁
		~HashTable()
		{
			int hashi = 0;
			Node* cur;
			Node* next;

			while (hashi < _tables.size())
			{
				cur = _tables[hashi];
				while (cur)
				{
					 next = cur->_next;
					delete cur;
					cur = next;
				}


				++hashi;
			}

		}

		Iterator Begin()
		{
			if (_n == 0)
				return End();
			int hashi = 0;

			while (hashi <= _tables.size() && _tables[hashi] == nullptr)
			{
				++hashi;
			}

			if (hashi >= _tables.size())
			{
				return Iterator(nullptr, this);
			}
			else
			{
				return Iterator(_tables[hashi],this);
			}
		}

		Iterator End()
		{
			return Iterator(nullptr, this);
		}

		ConstIterator Begin()const
		{
			int hashi = 0;

			while (hashi <= _tables.size() && _tables[hashi] == nullptr)
			{
				++hashi;
			}

			if (hashi >= _tables.size())
			{
				return ConstIterator(nullptr, this);
			}
			else
			{
				return ConstIterator(_tables[hashi],this);
			}
		}

		ConstIterator End()const
		{
			return ConstIterator(nullptr, this);
		}


		// 插入值为data的元素，如果data存在则不插入
		pair<Iterator,bool> Insert(const T& data)
		{
			KeyOfT kot;
			Iterator ret(nullptr,this);
			ret = Find(kot(data));
			if (ret._node != nullptr)
			{
				return make_pair(ret,false);
			}
			//负载因子过高，进行扩容
			if (_n * 10 / _tables.size() >= 10)
			{
				HashTable<K, T, KeyOfT> newtable;
				int newsize = _tables.size() * 2;
				newtable._tables.resize(newsize);

				for (auto& e : _tables)
				{
					Node* del = e;
					while (e)
					{
						newtable.Insert(e->_data);
						e = e->_next;
					}
					del = nullptr;
				}

				//调用自己类Insert遵循规则插入新表，最后交换
				_tables.swap(newtable._tables);
			}

			Hash hashfun;
			int hashi = hashfun(kot(data)) % _tables.size();

			Node* newnode = new Node(data);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			ret._node = newnode;

			++_n;
			return make_pair(ret,true);
		}

		// 在哈希桶中查找值为key的元素，存在返回true否则返回false﻿
		Iterator Find(const K& key)
		{
			KeyOfT kot;
			Hash hashfun;
			int hashi = hashfun(key) % _tables.size();

			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					return Iterator(cur,this);
				}
				cur = cur->_next;
			}
			return Iterator(nullptr,this);
		}

		// 哈希桶中删除key的元素，删除成功返回true，否则返回false
		bool Erase(const K& key)
		{
			KeyOfT kot;
			Hash hashfun;
			int hashi = hashfun(key) % _tables.size();

			Node* cur = _tables[hashi];
			Node* parent = nullptr;
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					Node* next = cur->_next;
					if (cur == _tables[hashi])
					{
						_tables[hashi] = next;
					}
					else
					{
						parent->_next = next;
					}

					delete cur;
					--_n;
					return true;
				}
				parent = cur;
				cur = cur->_next;
			}
			return false;
		}

	private:
		vector<Node*> _tables;  // 指针数组
		size_t _n = 0;			// 表中存储数据个数
	};





}



